#include "BinaryTree.h"
#include "Queue.h"

TreeNode* TreeNodeCreate(BTDataType val) {
    TreeNode* newTreeNode = MALLOC(TreeNode, 1);
    newTreeNode->val = val;
    newTreeNode->left = newTreeNode->right = NULL;
    return newTreeNode;
}

bool TreeEmpty(TreeNode* root) {
    return root == NULL;
}

bool IsLeaf(TreeNode* root) {
    assert(root);
    return root->left == NULL && root->right == NULL; 
}

// 二叉树销毁
void TreeDestory(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeDestory(root->left);
    TreeDestory(root->right);
    TreeDestory(root);
}
// 二叉树节点个数
int TreeSize(TreeNode* root) {
    // if (root == NULL) {
    //     return 0;
    // }
    // int n = 0;
    // Queue* queue = QueueInit();
    // Enqueue(queue, root);
    // while (!QueueEmpty(queue)) {
    //     TreeNode* cur = Dequeue(queue);
    //     n++;
    //     if (cur->left) {
    //         Enqueue(queue, cur->left);
    //     }
    //     if (cur->right) {
    //         Enqueue(queue, cur->right);
    //     }
    // }
    // return n;

    return TreeEmpty(root) ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);

}
// 二叉树叶子节点个数
int TreeLeafSize(TreeNode* root) {
    // if (root == NULL) {
    //     return 0;
    // }
    // int n = 0;
    // Queue* queue = QueueInit();
    // Enqueue(queue, root);
    // while (!QueueEmpty(queue)) {
    //     TreeNode* cur = Dequeue(queue);
    //     if (IsLeaf(cur)) {
    //         n++;
    //     }
    //     if (cur->left) {
    //         Enqueue(queue, cur->left);
    //     }
    //     if (cur->right) {
    //         Enqueue(queue, cur->right);
    //     }
    // }
    // return n;

    return root ? IsLeaf(root) ? 1 : TreeLeafSize(root->left) + TreeLeafSize(root->right) : 0;
    
}
// 二叉树第k层节点个数
int TreeLevelKSize(TreeNode* root, int k);
// 二叉树查找值为x的节点
TreeNode* TreeFind(TreeNode* root, BTDataType x) {

    if (root == NULL) {
        return NULL;
    }
    Queue* queue = QueueInit();
    Enqueue(queue, root);
    while (!QueueEmpty(queue)) {
        TreeNode* cur = Dequeue(queue);
        if (cur->val == x) {
            return cur;
        }
        if (cur->left) {
            Enqueue(queue, cur->left);
        }
        if (cur->right) {
            Enqueue(queue, cur->right);
        }
    }
    return NULL;

    // if (root == NULL) {
    //     return NULL;
    // }

    // if (root->val = x) {
    //     return root;
    // }

    // TreeNode* left = TreeFind(root->left, x);
    // if(left) {
    //     return left;
    // }

    // TreeNode* right = TreeFind(root->right, x);
    // if(right) {
    //     return right;
    // }
}

// 二叉树前序遍历 
void PreOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->val);
    PreOrder(root->left);
    PreOrder(root->right);
}

// 二叉树中序遍历
void InOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    InOrder(root->left);
    printf("%d ", root->val);
    InOrder(root->right);
}

// 二叉树后序遍历
void PostOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->val);
}

// 层序遍历
void LevelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Queue* queue = QueueInit();
    Enqueue(queue, root);
    while (!QueueEmpty(queue)) {
        TreeNode* cur = Dequeue(queue);
        printf("%d ", cur->val);
        if (cur->left) {
            Enqueue(queue, cur->left);
        }
        if (cur->right) {
            Enqueue(queue, cur->right);
        }
    }
    QueueDestroy(queue);
}

void TreeShow(TreeNode* root, void (*show)(TreeNode*)) {
    printf("[ ");
    show(root);
    printf("]\n");
}


// 判断二叉树是否是完全二叉树
bool TreeCompleteBFS(TreeNode* root) {
    if (root == NULL) {
        return true;
    }

    bool flag = false;
    Queue* queue = QueueInit();
    Enqueue(queue, root);
    while (!QueueEmpty(queue)) {
        TreeNode* cur = Dequeue(queue);
        if (cur->left) {
            if (flag) {
                QueueDestroy(queue);
                return false;
            }
            Enqueue(queue, cur->left);
        } else {
            flag = true;
        }
        if (cur->right) {
            if (flag) {
                QueueDestroy(queue);
                return false;
            }
            Enqueue(queue, cur->right);
        } else {
            flag = true;
        }
    }
    QueueDestroy(queue);
    return true;
}

bool TreeCompleteDFSInner(TreeNode* root, int index, int total) {
    if (root == NULL) {
        return true;
    }

    if (index >= total) {
        return false;
    }

    return TreeCompleteDFSInner(root->left, index * 2 + 1, total) && TreeCompleteDFSInner(root->right, index * 2 + 2, total);
}

bool TreeCompleteDFS(TreeNode* root) {
    return TreeCompleteDFSInner(root, 0, TreeSize(root));
}